import java.util.ArrayList;

class Solution {
    public int lengthOfLIS(int[] nums) {
        ArrayList<Integer> arr=new ArrayList<>();

        arr.add(nums[0]);
        for(int i=1;i<nums.length;i++){
            int num=nums[i];
            int sz=arr.size();
            int j=0;
            while(j<sz){
                int n=arr.get(j++);
                if(num>n){
                    if(j==sz) arr.add(num);
                }else{
                    arr.set(j-1,num);
                    break;
                }

            }

        }
        return arr.size();
    }
}


class Solution1 {
    public boolean increasingTriplet(int[] nums) {
        int[] arr=new int[3];
        arr[0]=nums[0];
        arr[1]=Integer.MAX_VALUE;
        for(int i=1;i<nums.length;i++){
            if(nums[i]<arr[0]) arr[0]=nums[i];
            else if(nums[i]>arr[0]){
                if(nums[i]>arr[1]) return true;
                if(nums[i]<arr[1]) arr[1]=nums[i];
            }
        }
        return false;
    }
}


class Solution2 {
    public int findLengthOfLCIS(int[] nums) {
        int min=nums[0];
        int ret=0;
        int count=0;
        for(int i=1;i<nums.length;i++){
            ret=Math.max(ret,count+1);
            count=0;

            while(i<nums.length&&nums[i-1]<nums[i]){
                count++;
                i++;
            }


        }
        ret=Math.max(ret,count+1);
        return ret;
    }
}


class Solution3 {
    public int maxProfit(int[] prices) {
        int ret=0;


        for(int i=0;i<prices.length-1;i++){
            int n=prices[i+1]-prices[i];
            if(n>0) ret+=n;
        }

        return ret;

    }
}